public class 不同的子序列 {
    public int numDistinct(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int n = s.length;
        int m = t.length;
        //创建二维动态规划表
        int[][] dp = new int[n + 1][m + 1];
        //处理边界条件
        for(int i = 0;i <= n;i++){
            dp[i][0] = 1;
        }
        //开始填表
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                dp[i][j] += dp[i - 1][j] + (s[i - 1] == t[j - 1] ? dp[i - 1][j - 1] : 0);
            }
        }
        return dp[n][m];
    }
}
